Shortest path problem is important for many applications in engineering, logistics and other sciences. Usually, a network consisting of a number of nodes and arcs which connect the nodes is considered. Certain costs are associated with the arcs to describe distance, travel time and/or other measurement of the arcs. Given a starting node and a destination node, the general problem is to find a path connecting the two nodes and at the same time minimizing the cost of the path. In most cases, all parameters including the structure of the network and costs of arcs are assumed fixed and known, and such problem is referred to as a Deterministic Problem (DP).
Although the algorithms for the determination of the shortest path in a deterministic problem are quite efficient, the real-world problems are always far from deterministic. For example, the travel time within a transportation network is always stochastic and/or time-dependent. Hence, the solution of a deterministic problem may have poor performance in a stochastic setting.
Furthermore, the cost of path such as the travel time, for example, within a traffic network is subject to uncertainty. Typically, the uncertainty is modeled using a random variable. A common assumption in conventional techniques for determining optimal paths in stochastic networks is that the distribution function of the underlying uncertain factor such as the travel time is known no matter stationary or time-varying. The distribution function plays an important role, for example, in the computation of the distribution of total travel time and the probability of fulfilling certain travel time target. In reality the distribution function may not be accurate as it is obtained from limited historical data, and sometimes the distribution is totally unavailable. In such cases, the performance of a solution that is tuned according to a presumed distribution can deteriorate a lot in practice.